package 归并排序

var assist []int

func less(v int, w int) bool {
	return v < w
}

func exch(a []int, i int, j int) {
	t := a[i]
	a[i] = a[j]
	a[j] = t
}

func sort(a []int) {
	//1.初始化辅助数组assist
	assist = make([]int, len(a))
	//2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引
	lo := 0
	hi := len(a) - 1
	sortRange(a, lo, hi)
}

func sortRange(a []int, lo int, hi int) {
	if hi <= lo {
		return
	}

	mid := lo + (hi-lo)/2
	sortRange(a, lo, mid)
	sortRange(a, mid+1, hi)
	merge(a, lo, mid, hi)
}

func merge(a []int, lo int, mid int, hi int) {
	//定义三个指针
	i := lo
	p1 := lo
	p2 := mid + 1

	//遍历: 移动p1指针和p2指针, 比较对应索引处的值, 找出小的那个, 放大负数数组的对应位置
	for p1 <= mid && p2 <= hi {
		if less(a[p1], a[p2]) {
			assist[i] = a[p1]
			i++
			p1++
		} else {
			assist[i] = a[p2]
			i++
			p2++
		}
	}

	//遍历：如果p1的指针没有走完, 那么顺序移动p1指针, 只剩余元素放辅助数组
	for p1 <= mid {
		assist[i] = a[p1]
		i++
		p1++
	}
	//遍历：如果p2的指针没有走完, 那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引位置
	for p2 <= hi {
		assist[i] = a[p2]
		i++
		p2++
	}

	//把辅助数组中的元素拷贝到原数组中
	for index := lo; index <= hi; index++ {
		a[index] = assist[index]
	}
}
